package main

//#link: https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
func main() {

}

//二维前缀和 sum[i][j]表示从(0,0)到(i,j)的区域大小和
type NumMatrix struct {
	sum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	sum := make([][]int, len(matrix)+1)
	for i := 0; i < len(sum); i++ {
		sum[i] = make([]int, len(matrix[0])+1)
	}
	for row := 1; row <= len(matrix); row++ {
		for col := 1; col <= len(matrix[0]); col++ {
			sum[row][col] = sum[row-1][col] + sum[row][col-1] + matrix[row-1][col-1] - sum[row-1][col-1]
		}
	}
	return NumMatrix{
		sum: sum,
	}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	row1++
	col1++
	row2++
	col2++
	return this.sum[row2][col2] - this.sum[row1-1][col2] - this.sum[row2][col1-1] + this.sum[row1-1][col1-1]
}
